package 题目集.树.构建树;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

//后序中序构建树输出层序遍历
//https://pintia.cn/problem-sets/1728617645410041856/exam/problems/1728617696303685641?type=7&page=0
public class 后序中序构建树 {
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int[] post=new int[n];
        int[] inorder=new int[n];
        for (int i = 0; i < n; i++) {
            post[i]=sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            inorder[i]=sc.nextInt();
        }

        Tree root=build(inorder,post,0,0,n);
        Queue<Tree> queue=new LinkedList<>();
        queue.add(root);
        StringBuilder str=new StringBuilder();
        while (!queue.isEmpty()) {
            Tree curr = queue.poll();
            if (curr==null){
                continue;
            }
            str.append(curr.val+" ");
            queue.add(curr.left);
            queue.add(curr.right);
        }
        System.out.println(str.substring(0, str.length() - 1));
    }

    public static Tree build(int[] inorder,int[] post,int inorderStart,int postorderStart,int len){
        if (len<1){
            return null;
        }
        Tree root = new Tree(post[postorderStart+len-1]);
        int rootIndex=-1;   //中序的根节点位置
        for (int i = inorderStart; i < inorderStart + len; i++) {
            if (root.val==inorder[i]){
                rootIndex=i;
                break;
            }
        }
        root.left=build(inorder,post,inorderStart,postorderStart,rootIndex-inorderStart);
        root.right=build(inorder,post,rootIndex+1,postorderStart+rootIndex-inorderStart,inorderStart+len-rootIndex-1);
        return root;
    }
    static class Tree{
        int val;
        Tree left;
        Tree right;

        public Tree(int val) {
            this.val = val;
        }
    }
}
